package cn.fatgod.learn.mybatis.math;

import java.util.ArrayList;
import java.util.List;

public class FillMatrix {

    public static int[][] fillMatrix(int[] nums, int target) {
        int[][] matrix = new int[3][3];
        if (nums.length != 9) {
            throw new IllegalArgumentException("输入的nums数组长度不为9！");
        }

        List<Integer> permutation = new ArrayList<>();
        for (int num : nums) {
            permutation.add(num);
        }

        boolean found = false;
        found = fillMatrixHelper(matrix, 0, 0, permutation, target);

        if (!found) {
            throw new IllegalArgumentException("无法找到符合条件的填充矩阵！");
        }

        return matrix;
    }

    private static boolean fillMatrixHelper(int[][] matrix, int row, int col, List<Integer> permutation, int target) {
        if (row == 3) {
            return checkMatrix(matrix, target);
        }

        for (int i = 0; i < permutation.size(); i++) {
            int num = permutation.get(i);
            permutation.remove(i);
            matrix[row][col] = num;
            int nextCol = (col + 1) % 3;
            int nextRow = row + (col + 1) / 3;
            if (fillMatrixHelper(matrix, nextRow, nextCol, permutation, target)) {
                return true;
            }
            permutation.add(i, num);
        }

        return false;
    }

    private static boolean checkMatrix(int[][] matrix, int target) {
        for (int i = 0; i < 3; i++) {
            int rowSum = matrix[i][0] + matrix[i][1] + matrix[i][2];
            int colSum = matrix[0][i] + matrix[1][i] + matrix[2][i];
            if (rowSum != target || colSum != target) {
                return false;
            }
        }

        int diagonalSum1 = matrix[0][0] + matrix[1][1] + matrix[2][2];
        int diagonalSum2 = matrix[0][2] + matrix[1][1] + matrix[2][0];

        return diagonalSum1 == target && diagonalSum2 == target;
    }

    public static void main(String[] args) {
        int[] nums = {14,12,4,6,20,10,8,0,16};
        int target = 30;

        try {
            int[][] result = fillMatrix(nums, target);
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    System.out.print(result[i][j] + " ");
                }
                System.out.println();
            }
        } catch (IllegalArgumentException e) {
            System.out.println(e.getMessage());
        }
    }
}